package q501_findMode;

import CommonClass.Common.TreeNode;

import java.util.*;

public class Solution_1 {

    /*
    暴力解法
    利用一个map记录在中序遍历过程中所有数值出现的次数
    然后将其按value排序后
    取出前面都为最大值的数
    再加入一个数组中
     */
    public int[] findMode(TreeNode root) {
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        Deque<TreeNode> stack = new LinkedList<TreeNode>();
        TreeNode node = root;
        while (!stack.isEmpty() || node != null){
            // 不停的将左子节点加入栈中
            while (node != null) {
                stack.push(node);
                node = node.left;
            }
            node = stack.pop();
            map.put(node.val, map.getOrDefault(node.val, 0) + 1);
            node = node.right;
        }
        List<Map.Entry<Integer, Integer>> temp = new ArrayList<Map.Entry<Integer, Integer>>(map.entrySet());
        Collections.sort(temp, new Comparator<Map.Entry<Integer, Integer>>() {
            public int compare(Map.Entry o1, Map.Entry o2) {
                return (int) o2.getValue() - (int)o1.getValue();
            }
        });
        List<Integer> resList = new ArrayList<Integer>();
        resList.add(temp.get(0).getKey());
        for (int i = 1; i < temp.size(); i++) {
            if (temp.get(i).getValue() == temp.get(0).getValue()) {
                resList.add(temp.get(i).getKey());
            }
        }
        int[] res = new int[resList.size()];
        for (int i = 0; i < resList.size(); i++) {
            res[i] = resList.get(i);
        }
        return res;
    }
}
